package sort;

public class QuickSort {	
	public static long Sort(int[] list){
		long startTime = System.currentTimeMillis();
		IterativeSort(list, 0, list.length-1);

		return System.currentTimeMillis()-startTime;
	}
	
	public static void IterativeSort(int[] list, int left, int right){
		//If list is small, just sort it with some simple algo
		if(right-left < 10){
			InsertionSort.particialSort(list, left, right+1);
			return;
		}
		
		int pivot = partition(list, left, right);
		IterativeSort(list, left, pivot-1);
		IterativeSort(list, pivot+1, right);
	}
	
	public static int partition(int[] list, int left, int right) {
		int storeIndex = left, pivotValue = list[right];

		for(int i=left; i<right; i++)
			if(list[i] <= pivotValue) SortTest.swap(list, i, storeIndex++);
		SortTest.swap(list, storeIndex, right);

		return storeIndex;
	}
}